package h0908;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 数组中第k个最大元素
 * @date 2024/9/8 23:10
 */
public class TheKthMaxNumInArray {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        System.out.println(findKthLargest(nums, 2));
    }

    public static int findKthLargest(int[] nums, int k) {
        if (nums.length == 1 && k == 1) return nums[0];
        if (k > nums.length || k < 1) return -1;
        //找到他的下标是n-2
        return getRes(nums, 0, nums.length - 1, k);
    }

    private static int getRes(int[] nums, int low, int high, int k) {
        if (low <= high) {
            int mid = partition(nums, low, high);
            if (mid == nums.length - k) {
                return nums[mid];
            } else if (mid > nums.length - k) {
                return getRes(nums, low, mid - 1, k);
            } else {
                return getRes(nums, mid + 1, high, k);
            }
        }
        return -1;
    }

    private static int partition(int[] nums, int left, int right) {
        int start = left + 1;
        int end = right;
        int pivot = nums[left];
        while (start <= end) {
            while (start <= end && nums[start] <= pivot) {
                start++;
            }
            while (start <= end && nums[end] > pivot) {
                end--;
            }
            if (start >= end) {
                break;
            }
            swap(nums, start, end);
        }
        swap(nums, end, left);
        return end;
    }

    private static void swap(int[] nums, int start, int end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }
}
